package p1021to1030;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * 1030 Travel Plan (30)（30 分）
    easy ac
 */
public class Travel_Plan {
    static BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
    static class Info {
        int distance;
        int cost;
        Info(int distance, int cost) {
            this.distance = distance;
            this.cost = cost;
        }
    }
    static class Graph{
        private final int vertex;
        private final int edges;
        private final int end;
        private final int start;

        private final Info[][] tables;
        Graph() throws IOException {
            String[] split = reader.readLine().split(" ");
            this.vertex=Integer.valueOf(split[0]);
            this.edges=Integer.valueOf(split[1]);
            this.start=Integer.valueOf(split[2]);
            this.end=Integer.valueOf(split[3]);

            tables=new Info[vertex][vertex];
            for (int i = 0; i < edges; i++) {
                String[] lineInfo = reader.readLine().split(" ");
                int s=Integer.valueOf(lineInfo[0]);
                int e=Integer.valueOf(lineInfo[1]);
                int distance=Integer.valueOf(lineInfo[2]);
                int cost=Integer.valueOf(lineInfo[3]);
                tables[s][e]=new Info(distance,cost);
                tables[e][s]=new Info(distance,cost);
            }
        }
        Node bfs(){
            Node node = new Node(start);
            boolean[] checkTable=new boolean[vertex];
            PriorityQueue<Node> queue = new PriorityQueue<>();
            queue.add(node);
            while (!queue.isEmpty()){
                Node poll = queue.poll();
                if(poll.id==end){
                   return poll;
                }
                checkTable[poll.id]=true;
                for (int i = 0; i < vertex; i++) {
                    Info info = tables[poll.id][i];
                    if(info!=null&&!checkTable[i]){
                        Node newNode = new Node(i);
                        newNode.previous=poll;
                        newNode.distance=poll.distance+info.distance;
                        newNode.cost=poll.cost+info.cost;
                        queue.offer(newNode);
                    }
                }
            }
            return null;
        }
    }
    static class Node implements Comparable<Node>{
        int id;
        int distance;
        int cost;
        Node previous;

        Node(int id) {
            this.id = id;
        }

        @Override
        public int compareTo(Node o) {
            int compare=distance-o.distance;
            if(compare==0){
                compare=id-o.id;
            }
            return compare==0?cost-o.cost:compare;
        }
    }

    /**
     * 1030 Travel Plan (30)（30 分）
     easy ac
     */
    public static void main(String[] args) throws IOException {
        Graph graph = new Graph();
        Node bfs = graph.bfs();
        LinkedList<String> list=new LinkedList<>();
        list.addFirst(String.valueOf(bfs.cost));
        list.addFirst(String.valueOf(bfs.distance));
        while (bfs!=null){
            list.addFirst(String.valueOf(bfs.id));
            bfs=bfs.previous;
        }
        int last=list.size()-1;
        int start=0;
        for(String o:list){
            System.out.printf("%s%s",o,start==last?"\n":" ");
            start++;
        }
    }
}
